Leonov một trong 20 phi công Không quân Liên Xô được chọn tham gia nhóm huấn luyện phi hành gia đầu tiên vào năm 1960. Giống như đa số các phi hành gia, Leonov là đảng viên Đảng Cộng sản Liên Xô. Chuyến đi bộ trong không gian của ông ban đầu dự kiến thực hiện trong sứ mệnh Voskhod 1, nhưng đã bị hủy. Thay vào đó, cột mốc lịch sử ấy đã diễn ra trong sứ mệnh Voskhod 2. Ông ra ngoài con tàu vũ trụ trong vòng 12 phút 9 giây vào ngày 18 tháng 3 năm 1965, và vẫn được kết nối với tàu bằng một ống dây dài 4,8 mét.

Cuối chuyến đi bộ trong không gian, bộ đồ bảo hộ của Leonov bị phồng lên trong không gian chân không, khiến cho ông không thể trở vào khoang khóa không khí (airlock) được. Ông bèn mở một van cho phép giảm áp suất của bộ đồ và nhờ thế mới có thể an toàn trở vào trong khoang tàu. Trong chuyến hành trình, Leonov vẽ một bức phác họa tả cảnh mặt trời mọc trên quỹ đạo, trở thành tác phẩm mỹ thuật đầu tiên được tạo ra trong vũ trụ. Leonov dành 18 tháng huấn luyện không trọng lực để chuẩn bị cho sứ mệnh này.

Năm 1968, Leonov được bổ nhiệm làm chỉ huy của chuyến bay Soyuz 7K-L1 bay quanh Mặt Trăng. Sứ mệnh này đã bị hủy bởi vì mãi chưa đạt được một chuyến bay quanh Mặt Trăng nào thành công (chỉ sau này, Zond 7 và Zond 8 mới thành công) và sứ mệnh Apollo 8 của Hoa Kỳ đã chinh phục được thử thách này trong Cuộc đua chinh phục vũ trụ. Leonov được chọn làm người Liên Xô đầu tiên đặt chân xuống Mặt Trăng, bước ra khỏi con tàu LOK/N1. Dự án này cũng bị hủy bỏ. Leonov được cử làm chỉ huy sứ mệnh Soyuz 1971 để bay tới Salyut 1, trạm vũ trụ có người đồn trú đầu tiên trên thế giới, nhưng đội phi hành đoàn của ông đã bị thay bằng đội dự bị bởi một trong số các thành viên, phi hành gia Valery Kubasov, bị nghi ngờ mắc bệnh lao (thành viên còn lại là Pyotr Kolodin).

Leonov tiếp tục được chọn làm chỉ huy sứ mệnh tiếp theo bay lên Salyut 1, nhưng lại một lần nữa bị hủy bỏ sau thảm kịch của phi hành đoàn Soyuz 11 và trạm vũ trụ này đã không còn. Hai trạm Salyut tiếp theo (thực ra là trạm quân sự Almaz) cũng bị mất lúc phóng hoặc gặp sự cố sau khi phóng, phi hành đoàn của Leonov tiếp tục chờ đợi. Đến khi trạm Salyut 4 tới được quỹ đạo thành công thì Leonov đã bị chuyển sang một dự án khác quan trọng hơn.

Trong chuyến bay vào vũ trụ lần thứ hai của Leonov, ông đảm nhiệm vị trí chỉ huy sứ mệnh Soyuz 19, một sứ mệnh liên hợp Apollo-Soyuz 1975 - đấy là sứ mệnh vũ trụ đầu tiên chứng kiến sự hợp tác giữa Liên Xô và Hoa Kỳ. Trong sứ mệnh này, Leonov đã xây dựng được tình bạn bền lâu với chỉ huy bên phía Hoa Kỳ Thomas P. Stafford, Leonov còn trở thành cha đã đầu của con Stafford. Stafford đã đọc điếu văn tại lễ tang Leonov vào tháng 10 năm 2019.

Từ năm 1976 đến 1982, Leonov là chỉ huy của hội phi hành gia ("Phi hành gia trưởng") và là phó giám đốc Trung tâm Huấn luyện Phi hành gia Yuri Gagarin, nơi trông coi việc huấn luyện phi hành gia. Ông cũng là biên tập của tập bản tin dành cho phi hành gia "Sao Hải Vương". Năm 1992, ông nghỉ hưu.